// Created by WXX on 2021/12/5 14:42
#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>

using namespace std;

/**
 * 执行用时：32 ms, 在所有 C++ 提交中击败了80.37%的用户
 * 内存消耗：22.2 MB, 在所有 C++ 提交中击败了29.91%的用户
 */
typedef pair<double, int> PDI;

#define x first
#define y second

class Solution {
public:
    double mincostToHireWorkers(vector<int>& quality, vector<int>& wage, int k) {

        int n = quality.size();
        vector<PDI> q;
        for (int i = 0; i < n; i++) q.push_back({(double)wage[i] / quality[i], quality[i]});

        sort(q.begin(), q.end());

        double res = 1e18, sum = 0;
        priority_queue<int> heap;
        for (auto &w : q) {
            sum += w.y;
            heap.push(w.y);
            if (heap.size() > k) {
                sum -= heap.top();
                heap.pop();
            }
            if (heap.size() == k)
                res = min(res, sum * w.x);
        }
        return res;
    }
};

int main() {

    vector<int> quality = {10, 20, 5}, wage = {70, 50, 30};
    cout << Solution().mincostToHireWorkers(quality, wage, 2) << endl;  // 105

    return 0;
}
